#leetcode题目77：组合
#难度：中等

#组合，回溯，剪枝

from typing import List

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        ans = []
        path = []
        
        def dfs(i):
            d = k - len(path)
            if d == 0:
                ans.append(path.copy())
                return
            for j in range(i, d - 1, -1):
                path.append(j)
                dfs(j - 1)
                path.pop()
        
        dfs(n)
        return ans


#测试数据
n=4
k=2
#预期输出：[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]
solution=Solution()
print(solution.combine(n,k))



n=1
k=1
#预期输出：[[1]]
solution=Solution()
print(solution.combine(n,k))